/**
 * 剑指 Offer 62. 圆圈中最后剩下的数字
 * https://leetcode-cn.com/problems/yuan-quan-zhong-zui-hou-sheng-xia-de-shu-zi-lcof/
 */
public class Solutions_Offer_62 {
    public static void main(String[] args) {
//        int n = 5, m = 3;  // output: 3
        int n = 10, m = 17;  // output: 2

        int result = lastRemaining2(n, m);
        System.out.println(result);
    }

    /**
     * 迭代
     * 约瑟夫环：中国版丢手绢
     */
    public static int lastRemaining2(int n, int m) {
        // res 记录 F(n, m)，最终胜利者的编号
        // 只有一个人时，留下的一定是自己本身
        int res = 0;
        // 两个人时，才能玩丢手绢
        for (int i = 2; i <= n; i++) {
            // 递推公式：F(n, m) = (F(n − 1, m) + m) % n
            // res 就是 F(n - 1, m)，即前一轮留下的人
            res = (res + m) % i;
        }
        return res;
    }

    /**
     * 递归
     */
    public static int lastRemaining(int n, int m) {
        if (n == 1) {
            // 只有一个人时，只会留下他自己
            return 0;
        }
        // 递推公式
        // n：初始时报名的人数（0, 1, 2,..., n - 1）
        // m：报数到 m 的人出局，出局人的下一位从 1 继续报数
//        F(n, m) = (F(n − 1, m) + m) % n
//        F(n, m)：n 个人报数（从 1 开始报），每报到 m 的人出局，最终胜利者（只留下一个人时）的编号
        // 第 n 轮留下的人
        return (m + lastRemaining(n - 1, m)) % n;
    }
}
